leetcode/100-n/877. 石子游戏.md

超时解法1

from typing import List

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return self.dp(piles, 0, sum(piles))

    def dp(self, piles: List[int], score, total) -> bool:
        # print(piles,score,total)
        #亚历克斯胜利条件
        if score * 2 > total:
            return True
        #亚历克斯失败条件
        if len(piles) == 1 and score * 2 < total:
            return False

        now_piles = piles[:]
        if len(piles) % 2 == 0:
            #亚历克斯
            #head
            if self.dp(now_piles[1:], score + now_piles[0], total):
                return True
            #tail
            if self.dp(now_piles[:-1], score + now_piles[-1], total):
                return True
            return False
        else:
            #李
            #head
            if not self.dp(now_piles[1:], score, total):
                return False
            #tail
            if not self.dp(now_piles[:-1], score, total):
                return False
            return True
        # print('opp')

if __name__ == '__main__':
    obj = Solution()
    print(obj.stoneGame([7,7,12,16,41,48,41,48,11,9,34,2,44,30,27,12,11,39,31,8,23,11,47,25,15,23,4,17,11,50,16,50,38,34,48,27,16,24,22,48,50,10,26,27,9,43,13,42,46,24]))

超时解法2

from typing import List

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.piles = piles
        return self.dp(0, 0, 0, sum(piles))

    def dp(self, head, tail, score, total) -> bool:
        # print(head,tail,score,total)
        #亚历克斯胜利条件
        if score * 2 > total:
            return True
        listLen = len(self.piles) - head - abs(tail)
        #亚历克斯失败条件
        if listLen <= 1 and score * 2 < total:
            return False

        if listLen % 2 == 0:
            #亚历克斯
            #head
            if self.dp(head + 1, tail, score + self.piles[head - 1], total):
                return True
            #tail
            if self.dp(head, tail - 1, score + self.piles[tail - 1], total):
                return True
            return False
        else:
            #李
            #head
            if not self.dp(head + 1, tail, score, total):
                return False
            #tail
            if not self.dp(head, tail - 1, score, total):
                return False
            return True
        # print('opp')

if __name__ == '__main__':
    obj = Solution()
    # print(obj.stoneGame([5,3,4,5]))
    print(obj.stoneGame([7,7,12,16,41,48,41,48,11,9,34,2,44,30,27,12,11,39,31,8,23,11,47,25,15,23,4,17,11,50,16,50,38,34,48,27,16,24,22,48,50,10,26,27,9,43,13,42,46,24]))